
/*
回溯
连接：https://leetcode.cn/problems/valid-sudoku/description/
题目： 有效的数独


    利用三个数组来标记状态
    因为我们要判断一个数字不能出现在同一行，也不能出现在同一列，并且在同一个九宫格中也不能出现
    所以我们使用bool row[9][10] 来标记任意一行的某个数字是否出现，例如row[2][3]==false就代表在第2行没有出现数字3
    同理 bool col[9][10] 标记任意一列的某个数字是否出现。

    对于9个小九宫格中是否存在相同的数字，我们采用grid[3][3][10]的三维数组进行判断，grid[0][0][1]=false就代表第一个小九宫格中没有数字1
    而grid[i][j]下标让每一个小格子的下标除以3即可得到0-3的下标

*/
class Solution {
public:
    bool row[9][10];
    bool col[9][10];
    bool grid[3][3][10];
    bool isValidSudoku(vector<vector<char>>& board) {
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[0].size();j++)
            {
                if(board[i][j]!='.')
                {
                    int num = board[i][j]-'0';
                    if(row[i][num]||col[j][num]||grid[i/3][j/3][num])
                        return false;
                    row[i][num] = col[j][num] = grid[i/3][j/3][num]=true;
                }

            }
        }
        return true;
    }
};

